﻿#include<iostream>
#include<string.h>
#include<vector>
#include <ctype.h>
#include <algorithm> 
#include <deque>
#include <stack>
#include <cctype>
#include <map>
#include <algorithm>
#include <mutex>
#include <condition_variable>
#include <queue>
#include <unordered_map>

using namespace std;

using namespace std;

//int main()
//{
//	cout << "hello world" << endl;
//	int a;
//	int b = 20;
//
//	int& ra = a;
//	return 0;
//}

//int& Add(int a, int b)
//{
//	int c = a + b;
//	return c;
//}
//int main()
//{
//	int& ret = Add(1, 2);
//	Add(3, 4);
//	cout << "Add(1, 2) is :" << ret << endl;
//	return 0;
//}

//void f(int)
//{
//	cout << "f(int)" << endl;
//}
//void f(int*)
//{
//	cout << "f(int*)" << endl;
//}
//int main()
//{
//	/*f(0);
//	f(NULL);
//	f((int*)NULL);*/
//
//	cout << sizeof(nullptr) << endl;
//	return 0;
//
//}

//class A
//{
//public:
//	void PrintA()
//	{
//		cout << "Print()" << endl;
//	}
//private:
//	int _a;
//};
//int main()
//{
//	A* p = nullptr;
//	p->PrintA();
//	return 0;
//}

//bool is_leapyear(int year)
//{
//    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
//}
//int main() {
//    int year, month, day;
//    int sum = 0;
//    int arr[12] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30 };
//    cin >> year >> month >> day;
//
//    if (month <= 2)
//    {
//        sum += arr[month - 1] + day;
//        cout << day << endl;
//    }
//    else
//    {
//        for (int i = 0; i < month; i++)
//        {
//            sum += arr[i];
//        }
//        sum += day;
//        if (is_leapyear(year))
//            sum += 1;
//        cout << sum;
//    }
//}

//class Time
//{
//public:
//	Time()
//	{
//		_hour = 1;
//		_minute = 1;
//		_second = 1;
//		
//	}
//	Time(const Time& t)
//	{
//		_hour = t._hour;
//		_minute = t._minute;
//		_second = t._second;
//		cout << "Time::Time(const Time&)" << endl;
//	}
//private:
//	int _hour;
//	int _minute;
//	int _second;
//};
//class Date
//{
//private:
//	// 基本类型(内置类型)
//	int _year = 1970;
//	int _month = 1;
//	int _day = 1;
//	// 自定义类型
//	Time _t;
//};
//int main()
//{
//	Date d1;
//	Date d2(d1);
//	return 0;
//}

//class Date
//{
//public:
//	Date(int year, int minute, int day)
//	{
//		cout << "Date(int,int,int):" << this << endl;
//	}
//	Date(const Date& d)
//	{
//		cout << "Date(const Date& d):" << this << endl;
//	}
//	~Date()
//	{
//		cout << "~Date():" << this << endl;
//	}
//private:
//	int _year;
//	int _month;
//	int _day;
//};
//Date Test(Date d)
//{
//	Date temp(d);
//	return temp;
//}
//int main()
//{
//	Date d1(2022, 1, 13);
//	Test(d1);
//	return 0;
//}

//#include <iostream>
//using namespace std;
//bool is_leapyear(int year)
//{
//    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
//}
//int main() {
//
//    int year;
//    int day;
//    int month_day[13] = { 0,31,59,80,120,151,181,212,243,273,304,334,365 };
//    int month[12] = { 1,2,3,4,5,6,7,8,9,10,11,12 };
//    while (cin >> year >> day)
//    {
//        for (int i = 0; i < 12; i++)
//        {
//            if (day > month_day[i] && day <= month_day[i + 1])
//            {
//                day -= month_day[i];
//                printf("%04d-%02d-%02d\n", year, month[i], day);
//            }
//
//        }
//    }
//}
// 64 位输出请用 printf("%lld")


//#include <iostream>
//using namespace std;
//
//class Date
//{
//public:
//    // 获取某年某月的天数
//    int GetMonthDay(int year, int month)
//    {
//        int monthArray[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
//        //四年一润，百年不润，四百年再润
//        if (month == 2 && (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
//            return 29;
//        else
//            return monthArray[month];
//    }
//    Date(int year, int month, int day)
//    {
//        _year = year;
//        _month = month;
//        _day = day;
//    }
//    Date& operator+=(int day)
//    {
//        while (_day > GetMonthDay(_year, _month))
//        {
//            _day -= GetMonthDay(_year, _month);
//            _month++;
//            if (_month == 13)
//            {
//                ++_year;
//                _month = 1;
//            }
//        }
//        return *this;
//    }
//    int _year;
//    int _month;
//    int _day;
//};
//int main() {
//
//    int count = 0;
//    cin >> count;
//    int year, month, day, sum_day;
//    for (int i = 0; i < count; i++)
//    {
//        cin >> year >> month >> day >> sum_day;
//        Date d(year, month, day);
//        d += day;
//        year = d._year;
//        month = d._month;
//        day = d._day;
//
//        printf("%d-%.2d-%.2d\n", year, month, day);
//    }
//}

//class Date {
//public:
//    // 获取某年某月的天数
//    int GetMonthDay(int year, int month) {
//        int monthArray[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
//        //四年一润，百年不润，四百年再润
//        if (month == 2 && (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
//            return 29;
//        else
//            return monthArray[month];
//    }
//
//    Date(int year, int month, int day)
//    {
//        _year = year;
//        _month = month;
//        _day = day;
//    }
//
//    Date& operator+=(int day) {
//        *this = *this + day;
//
//        return *this;
//    }
//
//    // 日期+天数
//    Date operator+(int day) {
//        Date tmp(*this);
//
//        tmp._day += day;
//        while (tmp._day > GetMonthDay(tmp._year, tmp._month)) {
//            tmp._day -= GetMonthDay(tmp._year, tmp._month);
//            tmp._month++;
//            if (tmp._month == 13) {
//                ++tmp._year;
//                tmp._month = 1;
//            }
//        }
//
//        return tmp;
//    }
//    int _year;
//    int _month;
//    int _day;
//};
//int main() {
//
//    int count = 0;
//    cin >> count;
//    int year, month, day, sum_day;
//    for (int i = 0; i < count; i++) 
//    {
//        cin >> year >> month >> day >> sum_day;
//        Date d(year, month, day);
//        d += sum_day;
//
//        printf("%d-%.2d-%.2d\n", d._year, d._month, d._day);
//    }
//}

//int globalVar = 1;
//
//static int staticGlobalVar = 1;
//
//void Test()
//
//{
//
//	static int staticVar = 1;
//
//	int localVar = 1;
//
//	int num1[10] = { 1, 2, 3, 4 };
//
//	char char2[] = "abcd";
//
//	char* pChar3 = "abcd";
//
//	int* ptr1 = (int*)malloc(sizeof(int) * 4);
//
//	int* ptr2 = (int*)calloc(4, sizeof(int));
//
//	int* ptr3 = (int*)realloc(ptr2, sizeof(int) * 4);
//
//	free(ptr1);
//
//	free(ptr3);
//
//}



//1. 选择题：
//
//选项 : A.栈 B.堆 C.数据段(静态区) D.代码段(常量区)
//
//globalVar在哪里？____  staticGlobalVar在哪里？____
//
//staticVar在哪里？____  localVar在哪里？____
//
//num1 在哪里？____
//
//
//
//char2在哪里？____ * char2在哪里？___
//
//pChar3在哪里？____ * pChar3在哪里？____
//
//ptr1在哪里？____ * ptr1在哪里？____
//
//
//
//2. 填空题：
//
//sizeof(num1) = ____;
//
//sizeof(char2) = ____;   strlen(char2) = ____;
//
//sizeof(pChar3) = ____;   strlen(pChar3) = ____;
//
//sizeof(ptr1) = ____;


//int main()
//{
//	string a = "hello world";
//	string b = a;
//	if (a.c_str() == b.c_str())
//	{
//		cout << "true" << endl;
//	}
//	else
//		cout << "false" << endl;
//	string c = b;
//	c = "";
//	if (a.c_str() == b.c_str())
//	{
//		cout << "true" << endl;
//	}
//	else cout << "false" << endl;
//	a = "";
//	if (a.c_str() == b.c_str())
//	{
//		cout << "true" << endl;
//	}
//	else cout << "false" << endl;
//	return 0;
//}

//int main()
//
//{
//
//	string str("Hello Bit.");
//
//	str.reserve(111);
//
//	str.resize(5);
//
//	str.reserve(50);
//
//	cout << str.size() << ":" << str.capacity() << endl;
//
//	return 0;
//
//}

//int main()
//{
//	string strText = "How are you?";
//	string strSeparator = " ";
//	string strResult;
//
//	int size_pos = 0;
//	int size_prev_pos = 0;
//
//	while ((size_pos = strText.find_first_of(strSeparator, size_pos)) != string::npos)
//	{
//		strResult = strText.substr(size_prev_pos, size_pos - size_prev_pos);
//		cout << strResult << " ";
//		size_prev_pos = ++size_pos;
//	}
//
//	if (size_prev_pos != strText.size())
//	{
//		strResult = strText.substr(size_prev_pos, size_pos - size_prev_pos);
//		cout << strResult << " ";
//	}
//
//	cout << endl;
//	return 0;
//}

// how are 

//class Solution {
//public:
//    int StrToInt(string str) {
//        for (auto ch : str)
//        {
//            if (ch)
//        }
//    }
//};


//class Solution {
//public:
//    int firstUniqChar(string s) {
//        char arr[26] = "";
//        for (auto ch : s)
//        {
//            arr[ch - 'a']++;
//        }
//        for (int i = 0; i < s.size(); i++)
//        {
//            arr[s[i] - 'a'] == 1;
//            return i;
//        }
//        return -1;
//    }
//};
//
//int main()
//{
//    Solution ret;
//    int a = ret.firstUniqChar("loveleetcode");
//    cout << a << endl;
//    return 0;
//}

//int main()
//{
//    string s;
//    int count = 0;
//    cin >> s;
//    int pos = s.rfind(" ");
//    for (int i = pos + 1; i < s.size(); i++)
//    {
//        if (s[i] != '\0')
//        {
//            ++count;
//        }
//    }
//    cout << count << endl;
//
//    return 0;
//}

//class Solution
//{
//public:
//    bool isPalindrome(string s)
//    {
//        string str;
//        str.reserve(s.size());
//
//        for (char ch : s) {
//            if (isalnum(ch)) {
//                str += tolower(ch);
//            }
//        }
//        size_t left = 0;
//        size_t right = str.size() - 1;
//
//        while (left < right)
//        {
//            if (s[left] != s[right])
//                return false;
//            left++;
//            right--;
//        }
//        return true;
//    }
//};
//
//int main()
//{
//    Solution s;
//    cout << s.isPalindrome("A man, a plan, a canal: Panama") << endl;
//
//    return 0;
//}

//class Solution {
//public:
//    string reverseWords(string s) {
//        int len = s.length();
//        //双指针
//        int fast = 0, slow = 0;
//        char* arr = (char*)malloc(sizeof(len));
//
//        for (int i = 0; i < len; i++)
//        {
//            if (s[i] == ' ' || s[i] == '\0')
//            {
//                fast = i - 1;
//                while (slow < fast)
//                {
//                    swap(s.begin() , s.end() );
//                    --fast;
//                    ++slow;
//                }
//                slow = fast + 2;
//            }
//        }
//        return s;
//    }
//}

//class Solution {
//public:
//    string reverseStr(string s, int k) {
//        int fast=0, slow = 0;
//        while (fast < s.size())
//        {
//            fast = 2 * k - 1;
//            if (fast - slow + 1 == 2 * k)
//            {
//                reverse(s.begin()+fast, s.begin()+slow);
//            }
//            else if (fast - slow + 1 < k)
//            {
//                reverse(s.begin() + fast, s.begin() + slow);;
//            }
//            else if (fast - slow + 1 < 2 * k &&  fast - slow + 1 >= k)
//            {
//                reverse(s.begin() + fast, s.begin() + slow);
//            }
//            ++fast;
//        }
//        return s;
//    }
//};


//class Solution 
//{
//public:
//    string reverseStr(string s, int k) 
//    {
//        int fast = 0, slow=0;
//        for (int i = 0; i < s.size(); i += 2 * k)
//        {
//            fast += 2 * k;
//            reverse(s.begin() + slow, s.begin() + slow+k);
//            slow = fast;
//        }
//        return s;
//    }
//};
//
//int main()
//{
//    Solution s;
//    string str = s.reverseStr("abcdefg", 2);
//    cout << str << endl;
//    return 0;
//}

//#include<vector>
//
//using namespace std;
//string multiply_strings(string str1, string str2) {
//	int n1 = str1.size();
//	int n2 = str2.size();
//	if (n1 == 0 || n2 == 0)
//		return "0";
//	// will keep the result number in vector
//	// in reverse order
//	vector result(n1 + n2, 0);
//	// Below two indexes are used to find positions
//	// in result.
//	int i_n1 = 0;
//	int i_n2 = 0;
//	// Go from right to left in num1
//	for (int i = n1 - 1; i >= 0; i--) {
//		int carry = 0;
//		int n1 = str1[i] - '0';
//		// To shift position to left after every
//		// multiplication of a digit in num2
//		i_n2 = 0;
//		// Go from right to left in num2
//		for (int j = n2 - 1; j >= 0; j--) {
//			// Take current digit of second number
//			int n2 = str2[j] - '0';
//			// Multiply with current digit of first number
//			// and add result to previously stored result
//			// at current position.
//			int sum = n1 * n2 + result[i_n1 + i_n2] + carry;
//			// Carry for next iteration
//			carry = sum / 10;
//			// Store result
//			result[i_n1 + i_n2] = sum % 10;
//			i_n2++;
//		}
//		// store carry in next cell
//		if (carry > 0)
//			result[i_n1 + i_n2] += carry;
//		// To shift position to left after every
//		// multiplication of a digit in num1.
//		i_n1++;
//	}
//	// ignore '0's from the right
//	int i = result.size() - 1;
//	while (i >= 0 && result[i] == 0)
//		i--;
//	// If all were '0's - means either both or
//	// one of num1 or num2 were '0'
//	if (i == -1)
//		return "0";
//	// generate the result string
//	string s = "";
//	while (i >= 0)
//		s += to_string(result[i--]);
//	return s;
//}
//int main()
//{
//	string str1;
//	string str2;
//	cout << "Input two strings (consisting only of numbers) to multiply: ";
//	cin >> str1 >> str2;
//	cout << multiply_strings(str1, str2);
//	return 0;
//}

//class Solution {
//public:
//    string multiply(string num1, string num2) {
//        if (num1 == "0" || num2 == "0")
//            return "0";
//
//        //预留足够的空间
//        string str;
//        str.reserve(num1.size() + num2.size());
//        
//        int ans = 0;//进位
//        //int min_len = num1.size() < num2.size() ? num1.size() : num2.size();
//        int len = num2.size();
//
//        while (len--)
//        {
//            for (int i = num1.size() - 1; i > 0; i--)
//            {
//                int sum = (num1[i] - '0') * (num2[len] - '0') + ans;
//                ans = sum / 10;
//                sum %= 10;
//                str += (sum - '0');
//            }
//        }
//        cout << str << endl;
//    }
//};
//
//int main()
//{
//    Solution s;
//    string str = s.multiply("123", "456");
//    cout << str << endl;
//    return 0;
//}

//int main()
//{
//	std::string name("John");
//	std::string family("Smith");
//	name += " K. ";         // c-string
//	name += family;         // string
//	name += '\n';           // character
//
//	std::cout << name;
//	return 0;
//}

//int main()
//{
//	string s = "hello world";
//	int len = s.size();
//	cout << "len:" << s.size() << endl;
//	cout << "sizeof:" << sizeof(s) << endl;
//
//	for (int i = 0; i < len+1; i++)
//	{
//		cout << s[i];
//	}
//
//
//	return 0;
//}



//void insert(size_t pos, const char* str)
//{
//	assert(pos <= _size);
//
//	size_t len = strlen(str);
//	size_t end = _size + len;
//
//	if (_size + len > _capacity)
//	{
//		reserve( _size + len;)
//	}
//
//	while (end > pos)
//	{
//		_str[end + len] = _str[end];
//		--end;
//	}
//
//	strncpy(_str + pos, s, len);
//
//	_size += len;
//	strncpy(_)
//
//	// 挪动数据
//
//	// 拷贝插入
//}

//int main()
//{
//	string s1("hello ");
//	cout << sizeof(s1) << endl;
//
//	return 0;
//}

//int main()
//{
	//vector<int> v1;
	//int a[4] ={0};
	//for (int i = 0; i < 4; ++i)
	//{
	//	cin >> a[i];
	//	v1.push_back(a[i]);
	//}

	//for (int i = 0; i < v1.size(); ++i)
	//{
	//	cout << v1[i] << " ";
	//}
	//cout << endl << v1.size();
//	string s = "hello world handsome man";
//
//	vector<string> s1;
//	s1.push_back(s);
//	toupper(s1[0]);
//	
//	return 0;
//}
//int main()
//{
//vector<int> i1(10, 42);
//vector<int> i2{ 42,42,42,42 };
//vector<int> i3;
//cout << endl;
//for (int i = 1; i < 10; ++i)
//{
//i3.push_back(i);
//}
//
//for (auto it = i3.begin(); it != i3. end(); ++it)
//{
//*it *= 2;
//}
//	
//
//for (auto it = i3.begin(); it != i3.end(); ++it)
//{
//cout << *it << " ";
//}
//return 0;
//};

//class Solution {
//public:
//    int minSubArrayLen(int target, vector<int>& nums) {
//        int len = 0;
//        int sum = 0;
//        for (int i = 0; i < nums.size(); ++i)
//        {
//            sum = 0;
//            for (int j = i; j < nums.size(); ++j)
//            {
//                //不断更新sum的值
//                sum += nums[j];
//                //找到大于target的连续下标
//                if (sum >= target)
//                {
//                    len = j - i +1;
//                }
//            }
//        }
//
//        return len;
//    }
//};
//
//int main()
//{
//    vector<int> nums = { 2,3,1,2,4,3 };
//    Solution s;
//    int len = s.minSubArrayLen(7, nums);
//
//    cout << len << endl;
//}

//#include <iostream>
//
//#include <vector>
//
//using namespace std;
//
//int main(void)
//
//{
//
//	vector<int>array;
//
//	array.push_back(100);
//
//	array.push_back(300);
//
//	array.push_back(300);
//
//	array.push_back(300);
//
//	array.push_back(300);
//
//	array.push_back(500);
//
//	vector<int>::iterator itor;
//
//	for (itor = array.begin(); itor != array.end(); itor++)
//
//	{
//		if (*itor == 300)
//
//		{
//
//			itor = array.erase(itor);
//
//		}
//
//	}
//
//	for (itor = array.begin(); itor != array.end(); itor++)
//
//	{
//
//		cout << *itor << " ";
//
//	}
//
//	return 0;
//
//}

//int main()
//{
//	int ar[] = {4,1,5,4,7,3,4,10 };
//	vector<int> v = {1,3,4,7,1,0,8,164,12,26};
//	std::sort(v.begin(), v.end());
//	//v.std::sort(v.begin(), v.end());
//	return 0;
//
//class Solution {
//public:
//    int singleNumber(vector<int>& nums)
//    {
//        sort(nums.begin(), nums.end());
//        int n = nums.size();
//        for (int i = 0; i < n; i += 3)
//        {
//            if (i == n - 1 || nums[i] != nums[i + 1])
//            {
//                return  nums[i];
//            }
//        }
//        return 0;
//    }
//};

//int main()
//{
//	vector<int> v{ 1, 2, 3, 4 };
//	auto it = v.begin();
//	while (it != v.end())
//	{
//		if (*it % 2 == 0)
//			v.erase(it);
//		++it;
//	}
//
//	for (auto ch : v)
//	{
//		cout << ch << endl;
//	}
//
//	return 0;
//}

//int main()
//{
//	vector<int> v{ 1, 2, 3, 4 };
//	auto it = v.begin();
//	while (it != v.end())
//	{
//		if (*it % 2 == 0)
//			it = v.erase(it);
//		else
//			++it;
//	}
//
//	for (auto ch : v)
//	{
//		cout << ch << endl;
//	}
//	return 0;
//}

//int sumOfLeftLeaves(TreeNode* root)
//{
//	if (root == NULL)
//		return 0;
//	if (root->left != NULL && root->left->left == NULL && root->left->right == NULL)
//		return root->left->val + sumOfLeftLeaves(root->right);
//
//	return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
//}

//class Node
//{
//public:
//    Node(int x)
//        : val(x), next(NULL)
//    {};
//
//    int val;
//    Node* next;
//};
//
//class List
//{
//public:
//    List()
//        : head(NULL)
//    {};
//    Node* head;
//    int size;
//};
//
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//    List list;
//    //构建循环链表
//    while (cin >> n >> m)
//    {
//        list.size = n;
//        for (int i = 1; i <= n; ++i)
//        {
//            Node* node = new Node(i);
//            if (list.head == NULL)
//            {
//                list.head = node;
//            }
//            else
//            {
//                Node* tail = list.head;
//                while (tail->next != NULL)
//                {
//                    tail = tail->next;
//                }
//                tail->next = node;
//            }
//        }
//        Node* tail = list.head;
//        while (tail->next != NULL)
//        {
//            tail = tail->next;
//        }
//        tail->next = list.head;
//
//        //数到m删除该节点
//        while (list.size != 1)
//        {
//            Node* tmp = list.head;
//            for (int i = 1; i < m; ++i)
//            {
//                tmp = tmp->next;
//            }
//
//            if (tmp->next == list.head)
//            {
//                list.head = list.head->next;
//            }
//            tmp->next = tmp->next->next;
//            delete tmp->next;
//        }
//    }
//    return list.head->val;
//}

//﻿template<typename T>
//void removeDuplicates(list<T>& aList)
//{
//	T curValue;
//	list<T>::iterator cur, p;
//	cur = aList.begin();
//	while (cur != aList.end())
//	{
//		curValue = *cur;
//		//空白行 1
//		while (p != aList.end())
//		{
//			if (*p == curValue)
//			{
//				//空白行 2
//			}
//			else
//			{
//				p++;
//			}
//		}
//	}
//}

//int main()
//{
//	int a = 56;
//	int i = 4;
//	int flag = 1;
//	int sum = 0;
//
//
//	
//	return 0;
//}



//void AdjustDown(const vector<int>& a, int n, int parent)
//{
//	int child = parent * 2 + 1;
//	while (child < n)
//	{
//		if (a[child + 1] > a[child] && child + 1 < n)
//			++child;
//
//		//孩子大于父亲，继续向下调整
//		if (a[child] > a[parent])
//		{
//			swap(a[child], a[parent]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//			break;
//	}
//}
//
//void AdjustUp(const vector<int>& a, int child)
//{
//	int parent = (child - 1) / 2;
//
//	while (child > 0)
//	{
//		if (a[child] > a[parent])
//		{
//			swap(a[child], a[parent]);
//			child = parent;
//			parent = (child + 1) / 2;
//		}
//		else
//			break;
//	}
//}
//
//vector<int>& HeapCreap(const vector<int>& a)
//{
//	vector<int> v1;
//	for (size_t i = 0; i < a.size(); ++i)
//	{
//		v1.push_back(a[i]);
//		AdjustUp(v1, i);
//	}
//
//	return v1;
//}
//
//int main()
//{
//	vector<int> a = { 27,15,19,18,28,34,65,49,25,37 };
//	vector<int> ret = HeapCreap(a);
//
//	for (auto k : ret)
//	{
//		cout << k << " ";
//	}
//	cout << endl;
//}

//void Swap(int& a, int& b)
//{
//	int tmp = a;
//	a = b;
//	b = tmp;
//}
//
//void AdjustUp(vector<int>& a, int child)
//{
//	int parent = (child - 1) / 2;
//
//	while (child > 0)
//	{
//		if (a[child] > a[parent])
//		{
//			swap(a[child], a[parent]);
//			child = parent;
//			parent = (child - 1) / 2;
//		}
//		else
//			break;
//	}
//}
//
//void AdjustDown(vector<int>& a, int size, int parent)
//{
//	int child = parent * 2 + 1;
//
//	while (child < size)
//	{
//		if (child+1 < size && a[child + 1] > a[child])
//		{
//			++child;
//		}
//		if (a[child] > a[parent])
//		{
//			swap(a[child], a[parent]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//			break;
//	}
//}
//
//vector<int> CreatHeap(const vector<int>& a)
//{
//	vector<int> vi;
//	for (size_t i = 0; i < a.size(); ++i)
//	{
//		vi.push_back(a[i]);
//		AdjustUp(vi,i);
//	}
//
//	return vi;
//}
//
//void HeapPop(vector<int>& a)
//{
//	swap(a[0], a[a.size() - 1]);
//
//	a.pop_back();
//	AdjustDown(a, a.size(), 0);
//
//}
//
//int topK(const vector<int>& a)
//{
//	return a[0];
//}
//
//int main()
//{
//	vector<int> arr = { 1,285,8,16,187,1245,324,81,34,184891,64,134,1641,6464,13464,46413 };
//	vector<int> ret = CreatHeap(arr);
//
//	for (size_t i = 0; i < ret.size(); ++i)
//	{
//		cout << ret[i] << " ";
//	}
//	cout << endl;
//
//
//	//选出最大的三数
//	int top[3] = { 0 };
//	for (size_t i = 0; i < 3; ++i)
//	{
//		top[i] = topK(ret);
//		HeapPop(ret);
//	}
//
//
//	for (size_t i = 0; i < 3; ++i)
//	{
//		cout << top[i] << " ";
//	}
//	cout << endl;
//	return 0;
//}

//向上调整法
//void AdjustUp(vector<int>& a)
//{
//	int child = a.size() - 1;
//	int parent = (child - 1) / 2;
//
//	while (child >= 0)
//	{
//		if (a[child] > a[parent])
//		{
//			swap(a[child], a[parent]);
//			child = parent;
//			parent = (child - 1) / 2;
//		}
//		else
//			break;
//	}
//
//}
//
//向下调整法
//void AdjustDown(int* a, int size, int parent)
//{
//	int child = parent * 2 + 1;
//	while (child > 0)
//	{
//		if ( child + 1 < size && a[child + 1] > a[child])
//			++child;
//		if (a[child] > a[parent])
//		{
//			swap(a[child], a[parent]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//void HeapSort(int* a, int size)
//{
//	for (int i = size - 1; i > 0; --i)
//	{
//		swap(a[0], a[i]);
//		--size;
//		AdjustDown(a, size, 0);
//	}
//}
//
//int main()
//{
//	int arr[] = {1,285,8,16,187,1245,324,81,34,184891,64,134,1641,6464,13464,46413};
//	int size = sizeof(arr) / sizeof(int);
//
//	for (int i = (size -2) / 2 ; i >= 0; --i)
//	{
//		AdjustDown(arr, size, i);
//	}
//	for (auto k : arr)
//	{
//		cout << k << " ";
//	}
//	cout << endl;
//
//	HeapSort(arr, size);
//	for (auto k : arr)
//	{
//		cout << k << " ";
//	}
//	cout << endl;
//
//	return 0;
//}

//void inert(vector<int>& a)
//{
//	//gap = 1
//	for (int i = 0; i < a.size() - 1; ++i)
//	{
//		int end = i;
//		int tmp = a[end + 1];
//		while (end >= 0)
//		{
//			if (tmp < a[end])
//			{
//				a[end + 1] = a[end];
//				--end;
//			}
//			else
//				break;
//		}
//		a[end + 1] = tmp;
//	}
//}

//void shellsort(vector<int>& a)
//{
//	int gap = a.size();
//	while (gap)
//	{
//		gap /= 2;
//		for (int i = 0; i < a.size()-gap; ++i)
//		{
//			int end = i;
//			int tmp = a[end + gap];
//
//			while (end >= 0)
//			{
//				if (tmp > a[end])
//				{
//					a[end + gap] = a[end];
//					end -= gap;
//				}
//				else
//					break;
//			}
//
//			a[end + gap] = tmp;
//		}
//	}
//}
//
////直接插入排序
//void inert(vector<int>& a)
//{
//	int end = 0;
//	for(int i=0; i<a.size()-1; ++i)
//	{
//		int end = i;
//		int tmp = a[end + 1];
//		while (end >= 0)
//		{
//			if (tmp < a[end])
//			{
//				a[end + 1] = a[end];
//				--end;
//			}
//			else
//				break;
//		}
//
//		a[end + 1] = tmp;
//	}
//}
//
//int main()
//{
//	vector<int> arr = { 1,285,8,16,187,1245,324,81,34,184891,64,134,1641,6464,13464,46413 };
//	//shellsort(arr);
//	inert(arr);
//
//	for (auto k : arr)
//	{
//		cout << k << " ";
//	}
//	cout << endl;
//
//	return 0;
//}

//int main()
//
//{
//	list<int> cont = { 1, 2, 3, 4, 5 };
//	list<int>::iterator iter, tempIt;
//	for (iter = cont.begin(); iter != cont.end();)
//	{
//		tempIt = iter;
//		++iter;
//		cont.erase(tempIt);
//	}
//}

//int main()
//{
//	int arr[5] = { 1,2,3,4,5 };
//	cout << *(*(&arr + 1) - 1) << endl;
//	return 0;
//}

//void adjust_down(int parent)
//{
//	int child = parent * 2 + 1;
//
//	while (child < size() - 1)
//	{
//		if (child + 1 < size() - 1 && a[child + 1] > a[child])
//			++child;
//		if (a[child] > a[parent])
//		{
//			swap(a[child], a[parent]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//			break;
//	}
//}

//int main()
//{
//	printf("%s, %5.3s", "com", "computer");
//	return 0;
//}

#include <iostream>
#include <string>
using namespace std;

//int main()
//{
//	string str;
//	getline(cin, str);
//	cout << str << endl;
//	system("pause");
//	return 0;
//}

//int main()
//{
//	string s1 = "zz";
//	string s2 = "z";
//	
//	for (auto ch : s2)
//	{
//		string::iterator it = s1.begin();
//		while (it != s1.end())
//		{
//			if (*it == ch)
//				it = s1.erase(it);
//
//			if (!s1.empty())
//				++it;
//			else
//				break;
//		}
//	}
//
//	cout << s1;
//	return 0;
//}

//int main()
//{
//	string s1 = "they are students";
//	string s2 = "aeiou";
//	int arr[100] = { 0 };
//	for (size_t i = 0; i < s2.size(); ++i)
//	{                                                                                                                                                                                                                                            
//		arr[s2[i] - 'A']++;
//	}
//
//	string ret;
//	string::iterator it = s1.begin();
//	while (it != s1.end())
//	{
//		if (arr[(*it) - 'A'] == 0)
//			ret += *it;
//
//		++it;
//	}
//
//	cout << ret;
//	return 0;
//}

//int main()
//{
//	string s1 = "i like beijing";
//	string s2;
//
//	string::iterator end = s1.end();
//	while (end != s1.begin())
//	{
//		while (end != s1.begin() && *end != ' ')
//			--end;
//		auto it = ++end;
//
//		while (*it != ' ' && *it != '\0')
//		{
//			s2 += *it;
//			++it;
//		}
//	}
//
//	cout << s2;
//}

 //定义一个函数来倒置字符串中的一段
//void reversed(string& s, int l, int r) {
//    while (l < r) {
//        swap(s[l], s[r]);
//        l++;
//        r--;
//    }
//}
//
//// 定义一个函数来倒置字符串中的每个单词
//void reverseWords(string& s) {
//    int start = 0;
//    for (int end = 0; end < s.length(); end++) {
//        // 如果遇到空格或者结束符，就倒置前面的单词
//        if (s[end] == ' ') {
//            reversed(s, start, end - 1);
//            start = end + 1;
//        }
//    }
//    // 倒置最后一个单词
//    reversed(s, start, s.length() - 1);
//    // 倒置整个字符串
//    reversed(s, 0, s.length() - 1);
//}
//
//int main() {
//    string s = "l like beijing.";
//    reverseWords(s);
//    cout << s << endl;
//}

//int main()
//{
//	string s1;
//
//
//	return 0;
//}

//int main()
//{
//
//	int n=6;
//	int count = 0;
//	int arr[10000] = {1,2,3,2,2,1};
//
//	//cin >> n;
//	//for (int i = 0; i < n; ++i)
//	//{
//	//	cin >> arr[i];
//	//}
//
//	int flag = 0;//
//	for (size_t i = 1; i < n-1; ++i)
//	{
//		if (flag == 0)
//		{
//			//++i;
//			if (arr[i] > arr[i - 1])
//			{
//				flag = 1;
//			}
//			else if (arr[i] < arr[i - 1])
//			{
//				flag = -1;
//			}
//		}
//		else if (flag == 1) //递增序列
//		{
//			if (arr[i] <= arr[i + 1])
//				continue;
//			else //arr[i] > arr[i + 1]
//			{
//				flag = 0;
//			}
//		}
//		else if (flag == -1)
//		{
//			if (arr[i] >= arr[i + 1])
//				continue;
//			else //arr[i] < arr[i + 1]
//			{
//				flag = 0;
//			}
//		}
//
//	}
//
//	cout << count;
//}

//int number(const vector<int> arr)
//{
//	int left = 0, right = arr.size() - 1;
//	int mid = 0;
//
//	while (left < right)
//	{
//		if (right - left == 1)
//			return arr[right];
//
//		mid = (left + (right)) / 2;
//
//		if (arr[left] == arr[right] && arr[left] == arr[mid])
//		{
//			int res = arr[left];
//			for (int i = left + 1; i <= right - 1; ++i)
//			{
//				if (res > arr[i])
//					res = arr[i];
//			}
//
//			return res;
//		}
//
//		if (arr[mid] >= arr[left])
//			left = mid;
//		else 
//			right = mid;
//	}
//	return arr[mid];
//}
//int minNumberInRotateArray(vector<int> rotateArray) {
//    int left = 0, right = rotateArray.size() - 1;
//    int mid = 0;
//    int k = rotateArray[0];
//    while (left < right) {
//        if (right - left == 1)
//            return rotateArray[right];
//
//        mid = (left + (right)) / 2;
//
//        if (rotateArray[left] == rotateArray[right] && rotateArray[left] == rotateArray[mid]) {
//            int res = rotateArray[left];
//            for (int i = left + 1; i <= right - 1; ++i) {
//                if (res > rotateArray[i])
//                    res = rotateArray[i];
//            }
//
//            return res;
//        }
//
//        if (rotateArray[mid] >= rotateArray[left])
//            left = mid;
//            
//        else
//            right = mid;
//    }
//    return rotateArray[k];
//}

//vector<int> reOrderArrayTwo(vector<int>& array) {
//    // write code here
//    //双指针
//    int left = 0, right = array.size() - 1;
//    while (left < right)
//    {
//        while (left < right && array[left] % 2 == 0) //找偶数
//            ++left;
//        while (left < right && array[right] % 2 == 1) //找奇数
//            --right;
//        if (left < right)
//            swap(array[left], array[right]);
//    }
//
//    return array;
//}

//int main()
//{
//	vector<int> arr = {2,4,6};
//    vector<int> res = reOrderArrayTwo(arr);
//    for (int i = 0; i < res.size(); ++i)
//    {
//        cout << res[i];
//    }
//	return 0;
//}

//int f(int x)
//{
//	int count = 0;
//	while (x)
//	{
//		count++;
//		x = x & (x - 1);
//	}
//
//	return count;
//}

//struct A
//{
//	int a;
//	short b;
//	int c;
//	char d;
//};
//struct B
//{
//	int a;
//	short b;
//	char c;
//	int  d;
//
//};
//int cnt;
//int f(int n)
//{
//	cnt++;
//	if (n == 0)
//		return 1;
//	else if (n == 1)
//		return 2;
//	else
//		return f(n - 1) + f(n - 2);
//}
//
//int main()
//{
//	f(8);
//	cout << cnt;
//	return 0;
//
//}
//int main()
//{
//	int A_B, B_C, ab, bc;//A_B表示A-B,ab表示a+b
//	A_B = 0, B_C = 0, ab = 2, bc = 2;
//	//cin >> A_B >> B_C >> ab >> bc;
//	int A, B, C;
//
//	A = (A_B + ab) / 2;
//	B = (ab - A_B)/2;
//	C = (bc - B);
//	if (A - B == A_B && B-C == B_C && A + B == ab && B + C == bc)
//		printf("%d %d %d", A, B, C);
//	else
//		printf("no");
//}

//int main()
//{
//	int num=28, scale=2;
//	stack<int> s1;
//	const char* ptr = "abcdefghijklmnopqrstuvwxyz";
//	int flag = 0;//判断整数还是负数
//
//	if (num < 0)
//		flag = -1;
//
//	while (num / scale)
//	{
//		int ret = num % scale;
//		s1.push(ret);
//		num /= scale;
//	}
//
//	s1.push(num % scale);
//
//	while (!s1.empty())
//	{
//		if (-1 == flag)
//			cout << -1;
//		int ret = s1.top();
//		if (ret <= 9)
//			cout << ret;
//		else
//		{
//			cout << ptr[ret - 10] << endl;
//		}
//			s1.pop();
//	}
//	return 0;
//}

//int main()
//{
//	char p1[15] = "abcd", * p2 = "ABCD", str[50] = "xyz";
//	strcpy(str + 2, strcat(p1 + 2, p2 + 1));
//	printf("%s", str);
//	return 0;
//}

#pragma pack(8)
//struct one {
//	double a;
//	char b;
//	int c;
//};
//
//struct two {
//	char a;
//	double b;
//	int c;
//};
//
//int main()
//{
//	char dog[] = "wang\0miao";
//	cout << sizeof(dog) << endl;
//	cout << strlen(dog) << endl;
//}

//int main()
//{
//	int n;
//	int arr[100000];
//	cin >> n;
//	for (int i = 0; i < n; ++i)
//	{
//		cin >> arr[i];
//	}
//
//	for (int i = 0; i < n; ++i)
//	{
//		printf("%d", arr[i]);
//	}
//	
//	return 0;
//}

//int main()
//{
//	int arr[4] = { 0 };
//	return 0;
//}

//int main()
//{
//	int n;
//	cin >> n;
//
//	vector<int> a;
//	a.resize(n + 1);
//	a[n] = 0;
//	int i = 0, sum = 0, max = 0;
//	for (i = 0; i < n; ++i)
//		cin >> a[i];
//
//	i = 0;
//	while (i < n)
//	{
//		//非递减子序列
//		if (a[i] < a[i + 1])
//		{
//			sum = 0;
//			while (i < n && a[i] <= a[i + 1])
//			{
//				sum += a[i];
//				++i;
//			}
//
//			if (sum > max)
//				max = sum;
//			//++i;
//		}
//		else if (a[i] == a[i + 1])
//		{
//			while (i < n && a[i] == a[i + 1])
//			{
//				sum += a[i];
//				++i;
//			}
//			if (i < n && a[i] > a[i + 1])
//			{
//				while (i < n && a[i] > a[i + 1])
//				{
//					sum += a[i];
//					++i;
//				}
//			}
//			else
//			{
//				while (i < n && a[i] < a[i + 1])
//				{
//					sum += a[i];
//					++i;
//				}
//			}
//
//			if (sum > max)
//				max = sum;
//
//		}
//		else //非递增序列
//		{
//			sum = 0;
//			while (i < n && a[i] >= a[i + 1])
//			{
//				sum += a[i];
//				++i;
//			}
//
//			if (sum > max)
//				max = sum;
//			++i;
//		}
//	}
//
//	cout << max;
//}

//int main()
//{
//	int i = 1;
//	if (i <= 0)
//	{
//		printf("****\n");
//	}
//	else
//		printf("%%%%\n");
//	return 0;
//}
//int main()
//{
//	int w = 4, h = 2;
//	vector<vector<int>> arr;
//	arr.resize(w);
//	for (int i = 0; i < w; ++i)
//	{
//		arr[i].resize(h+1, 1);
//	}
//
//	for (int i = 0; i < arr.size(); ++i)
//	{
//		for (int j = 0; j < arr[0].size(); ++j)
//			cout << arr[i][j] << " ";
//		cout << endl;
//	}
//}

//bool is_leagl_postion(const vector<vector<int>>& arr, int i, int j)
//{
//    int up_postion = -1;
//    int left_postion = -1;
//
//    //判断该数的上两个位置以及左边两个位置是否存放物品，如果存放或者不存在置为1
//    if (i - 2 < 0 || arr[i - 2][j] == 1)
//        up_postion = 1;
//    if (j - 2 < 0 || arr[i][j - 2] == 1)
//        left_postion = 1;
//
//    if (left_postion && up_postion)
//        return false;
//
//    return true;
//}
//
//int main()
//{
///*    int w, h;
//    cin >> w >> h;
//    int count = 0;
//    vector<vector<int>> arr;
//    arr.resize(w + 1);
//    for (int i = 0; i < w; ++i)
//    {
//        arr[i].resize(h + 1, 1);
//    */
//
//    int row = 3;
//    int col = 2;
//    vector<vector<int>> vec;
//    vec.resize(row+1);
//    for (int i = 0; i < vec.size(); i++) {
//        vec[i].resize(col+1);
//    }
//    for (int i = 0; i < row; i++) {
//        for (int j = 0; j < col; j++) {
//            vec[i][j] = 1;
//        }
//    }
//
//    for (int i = 0; i < row; i++) {
//        for (int j = 0; j < col; j++) {
//            cout << vec[i][j] << " ";
//        }
//        cout << endl;
//    }
//
//    //for (int i = 0; i < row; i++) {
//    //    for (int j = 0; j < col; j++) {
//    //        cout << vec[i][j] << " ";
//    //    }
//    //    cout << endl;
//    //}
//
//
//
//    //for (int i = 0; i < arr.size(); ++i)
//    //{
//    //    for (int j = 0; j < arr[0].size(); ++j)
//    //    {
//    //        if (is_leagl_postion(arr, i, j))
//    //        {
//    //            arr[i][j] = 1;
//    //            ++count;
//    //        }
//    //    }
//    //}
//
// //   for (int i = 0; i < arr.size(); ++i)
//	//{
//	//	for (int j = 0; j < arr[0].size(); ++j)
//	//		cout << arr[i][j] << " ";
//	//	cout << endl;
//	//}
//
// //   cout << count;
//}

//int StrToInt(string str)
//{
//    if (str.length() == 0)
//        return 0;
//    stack<int> s1;
//    int num=0;
//    int flag = 1; //1代表正数，-1代表负数
//    string::iterator it = str.begin();
//    if (*it == '-' || *it == '+')
//    {
//        if (*it == '-')
//            flag = -1;
//        ++it;
//    }
//
//    //整数入栈
//    while (it != str.end())
//    {
//        if ((*it - '0') >= 0 && (*it - '0') <= 9)
//        {
//            s1.push(*it - '0');
//            ++it;
//        }
//        else
//            return 0;
//    }
//
//    int size = s1.size();
//    for (int i = 0; i < size; ++i)
//    {
//        int top = s1.top();
//        num += pow(10, i) * top;
//        s1.pop();
//    }
//    if (flag == -1)
//        num *= -1;
//
//    return num;
//}
//
//int main()
//{
//    string s1 = "+2147483647";
//    int tmp = StrToInt(s1);
//    cout << tmp; 
//    return 0;
//}

//template <class T>
//class Big {
//	long n;
//public:
//	Big(T i)
//		:n(i)
//	{}
//
//	Big operator+(Big b)
//	{
//		return Big(n + b, n);
//	}
//};
//
//int main()
//{
//
//}

//int main()
//{
//    int a = 0, b = 1;
//    int tmp = 0;
//    int num;
//    cin >> num;
//    int min;
//    while (num < a || num > b)
//    {
//        // 迭代
//        tmp = a + b;
//        a = b;
//        b = tmp;
//        if (num >= a && num <= b)
//        {
//            if (num - a <= b - num) //距离a近
//                min = num - a;
//            else
//                min = b - num;
//            break;
//        }
//    }
//    cout << min;
//    return 0;
//}

//int main()
//{
//	int a = 1;
//	int b = 2;
//	int& p = a;
//	p = b;
//	return 0;
//}
//class A
//{
//	static int n;
//public:
//	A()
//	{
//		n++;
//	}
//
//	~A()
//	{
//		n--;
//	}
//	static int get() { return n; }
//};
//
//int A::n = 0;
//int main()
//{
//	A* p = new A;
//	delete p;
//	cout << A::get() << " ";
//	return 0;
//}

//#include <iostream>
//#include <vector>
//#include <string>
//#include <algorithm>
//using namespace std;
//
//bool sort_bylength(const vector<string>& s)
//{
//    for (size_t i = 0; i < s.size() - 1; ++i)
//    {
//        if (s[i].size() > s[i + 1].size())
//            return false;
//    }
//    return true;
//}
//
//bool sort_bydictionary(const vector<string>& s)
//{
//    vector<string> tmp(s);
//    sort(tmp.begin(), tmp.end());
//    if (tmp == s)
//        return true;
//    else
//        return false;
//}
//
//int main()
//{
//    int n;
//    cin >> n;
//    vector<string> s;
//    s.resize(n);
//    for (int i = 0; i < n; ++i)
//    {
//        getline(cin, s[i]);
//    }
//    bool sort_length = sort_bylength(s);
//    bool sort_dictionary = sort_bydictionary(s);
//
//    if (sort_length == true && sort_dictionary == false)
//        cout << "lexicographically" << endl;
//    else if (sort_length == false && sort_dictionary == true)
//        cout << "lengths" << endl;
//    else if (sort_length && sort_dictionary)
//        cout << "both" << endl;
//    else
//        cout << "none" << endl;
//
//    return 0;
//
//}


//int Gcd(int M, int N)
//{
//	if (!N)
//		return M;
//	else
//		return Gcd(N, M % N);
//}
//
//int main()
//{
//	cout << Gcd(16,12) << endl;
//	return 0;
//}

//string replaceSpace(string s) {
//	for (int i = 0; i < s.size(); ++i)
//	{
//		if (s[i] == ' ')
//			s.insert(i, "%20");
//	}
//
//	return s;
//}
//int main()
//{
//	string s1 = "we are happy";
//	cout << replaceSpace(s1) << endl;
//}


//int main()
//{
//	string s1 = "hello world";
//	for (auto ch : s1)
//	{
//		cout << ch  ;
//	}
//	return 0;
//}

//int main()
//{
//	int n, m;
//	cin >> n >> m;
//
//	vector<vector<int>> arr;
//	arr.resize(m);
//
//	for (size_t i = 0; i < arr.size(); ++i)
//	{
//		arr[i].resize(n, 0);
//	}
//
//	for (int i = 0; i < m; ++i)
//	{
//		for (int j = 0; j < n; ++j)
//		{
//			cout << arr[i][j] << " ";
//		}
//		cout << endl;
//	}
//}

//int length_goal(const string& s)
//{
//    int goal = 0;
//    if (s.length() <= 4)
//        goal = 5;
//    else if (s.length() >= 5 && s.length() <= 7)
//        goal = 10;
//    else //s.length()>7
//        goal = 25;
//    return goal;
//}
//int alphabet_goal(const string& s)
//{
//    int lowercase = 0;// flag:是否有小写字母
//    int uppercase = 0;// flag:是否有大写字母
//    int goal = 0;
//    for (auto ch : s)
//    {
//        if (islower(ch) && lowercase == 0)
//            lowercase = 1;
//        if (isupper(ch) && uppercase == 0)
//            uppercase = 1;
//    }
//    if (lowercase == 1 && uppercase == 1)
//        goal = 20;
//    else if (lowercase == 1 || uppercase == 1)
//        goal = 10;
//    else // lowercase == 0 && uppercase == 0
//        goal = 0;
//    return goal;
//}
//int number_goal(const string& s)
//{
//    int count_number = 0;
//    int goal = 0;
//    for (auto ch : s)
//    {
//        if (count_number <= 1 && isdigit(ch))
//            ++count_number;
//    }
//    if (count_number == 0)
//        goal = 0;
//    else if (count_number == 1)
//        goal = 10;
//    else
//        goal = 20;
//    return goal;
//}
//int symbol(const string& s)
//{
//    int symbol_count = 0;
//    int goal = 0;
//    for (auto ch : s)
//    {
//        if (ch >= 0x21 && ch <= 0x2F || ch >= 0x3A && ch <= 0x40 || ch >= 0x5B && ch <= 0x60 ||
//            ch >= 0x7B && ch <= 0x7E)
//            ++symbol_count;
//    }
//    if (symbol_count == 0)
//        goal = 0;
//    else if (symbol_count == 1)
//        goal = 10;
//    else //symbol_count > 1
//        goal = 25;
//    return goal;
//}
//
//int reward(const string& s)
//{
//    int goal = 0;
//    if (alphabet_goal(s) == 20 && number_goal(s) && symbol(s))
//        goal = 5;
//    else if (alphabet_goal(s) == 10 && number_goal(s) && symbol(s))
//        goal = 3;
//    else if (alphabet_goal(s) == 10 && number_goal(s))
//        goal = 2;
//
//    return goal;
//
//}
//
//int main()
//{
//    string s1 = "Jl)M:+";
//    int goal = 0;
//    //getline(cin, s1);
//    goal += length_goal(s1);
//    goal += alphabet_goal(s1);
//    goal += number_goal(s1);
//    goal += symbol(s1);
//    goal += reward(s1);
//
//
//    if (goal >= 90)
//        cout << "VERY_SECURE" << endl;
//    else if (goal >= 80)
//        cout << "SECURE" << endl;
//    else if (goal >= 70)
//        cout << "VERY_STRONG" << endl;
//    else if (goal >= 60)
//        cout << "STRONG" << endl;
//    else if (goal >= 50)
//        cout << "AVERAGE" << endl;
//    else if (goal >= 25)
//        cout << "WEAK" << endl;
//    else
//        cout << "VERY_WEAK" << endl;
//}
//int ssearch(vector<int>& nums, int target) {
//	for (int i = 0; i < nums.size(); ++i)
//	{
//		if (nums[i] == target)
//			return i;
//	}
//	return 0;
//}
//int main()
//{
//	vector<int> nums = {5,7,7,8,8,10,8};
//	cout << ssearch(nums, 8) << endl;
//}

//int binInsert(int n, int m, int j, int i) {
//	// write code here
//	for (; j <= i; ++j)
//	{
//		int tmp = 1;
//		tmp &= m << j;
//		n &= tmp;
//	}
//	return n;
//}
//int main()
//{
//	cout << binInsert(1024, 19, 2, 6);
//	return 0;
//}

//bool is_prime_number(int x)
//{
//    for (int i = 2; i < x; ++i)
//    {
//        if (x % i == 0)
//            return false;
//    }
//    return true;
//}
//void serach_prime_number(vector<int>& arr, int n)
//{
//    for (int i = 0; i < n; ++i)
//    {
//        if (is_prime_number(i))
//            arr.push_back(i);
//    }
//}
//vector<int> serch_min_number(const vector<int>& arr, int target)
//{
//    int min = INT_MAX;
//    vector<int> ret(2);
//    int pre = 0, next = 1;
//    for (; pre < next; ++pre)
//    {
//        for (next = pre; next < arr.size() - 1; ++next)
//        {
//            if (arr[pre] + arr[next] == target)
//            {
//                if (arr[next] - arr[pre] < min)
//                {
//                    min = arr[next] - arr[pre];
//                    ret[0] = arr[pre];
//                    ret[1] = arr[next];
//                }
//            }
//        }
//    }
//    return ret;
//}
//
//int main()
//{
//    int num = 4;
//    vector<int> prime;
//    serach_prime_number(prime, num);
//    vector<int> ret = serch_min_number(prime, num);
//    for (auto k : ret)
//        cout << k << " ";
//    return 0;
//}

//vector<int> serach_factor(int x)
//{
//    vector<int> ret;
//    for (int i = 2; i < x; ++i)
//    {
//        if (x % i == 0)
//            ret.push_back(i);
//    }
//    return ret;
//}
//int count_jump(int N, int M)
//{
//    int count = 0;
//    vector<int> ret;
//    while (N < M)
//    {
//        ret = serach_factor(N);
//        if (N + ret[ret.size() - 1] < M)
//        {
//            N = ret[ret.size() - 1] + N;
//            ++count;
//        }
//        else
//        {
//            int size = ret.size() - 2;
//            while (N + ret[size] <= M)
//            {
//               
//                if (N + ret[size] == M)
//                {
//                    ++count;
//                    break;
//                }
//                --size;
//            }
//            break;
//        }
//    }
//    return count;
//
//}
//int main()
//{
//    int N = 4, M = 24;
//    cout << count_jump(N, M);
//    return 0;
//}

//int main()
//{
//	string s1;
//	getline(cin, s1);
//	cout << s1;
//	return 0;
//}

//int main()
//{
//    string s = "xcopy /s c:\\ d:\\e ";
//	s += " ";
//    string tmp = "";
//    vector<string> ret;
//    int count = 0;
//    //getline(cin, s);
//    int begin = 0, end = begin + 1;
//
//	while (begin < end && end < s.length())
//	{		while ((s[end + 1] != ' ' && s[end + 1] != '"') && end < s.length())
//		{
//			++end;
//		}
//		if (s[end + 1] == ' ')
//		{
//			int len = end - begin+1;
//			ret.push_back(s.substr(begin, len));
//			begin = end + 2;
//			end = begin + 1;
//		}
//		else if (s[begin] == '"') // 一定是前部分的双引号
//		{
//			while (s[end] != '"')
//				++end;
//			int len = end - begin;
//			ret.push_back(s.substr(begin + 1, len));
//			begin = end + 2;
//			end = begin + 1;
//		}
//	}
//
//
//    cout << ret.size() << endl;
//    for (int i = 0; i < ret.size(); ++i)
//    {
//        cout << ret[i] << endl;
//    }
//
//    return 0;
//}


//int main()
//{
//	int n;
//	cin >> n;
//	vector<int> arr(n);
//	for (int i = 0; i < n; ++i)
//	{
//		cin >> arr[i];
//	}
//
//	for (int i = 0; i < n; ++i)
//	{
//		cout <<  arr[i];
//	}
//}

//struct A
//{
//	void foo() { printf("foo"); }
//	virtual void bar() { printf("bar"); }
//	A() { bar(); }
//};
//
//struct B : A
//{
//	void foo() { printf("b_foo"); }
//	void bar() { printf("b_bar"); }
//};
//
//int main()
//{
//	A* p = new B;
//	p->foo();
//	p->bar();
//	return 0;
//}

//bool Double_joker(const string& s) //王炸
//{
//    if (s.find("joker JOKER") != string::npos)
//        return true;
//    return false;
//}
//
//string FindMax(const string& s1, const string& s2)
//{
//    if (Double_joker(s1))
//        return s1;
//    if (Double_joker(s2))
//        return s2;
//
//    string sort_poker = "345678910JQKA2jokerJOKER";
//    //记录两张手牌的第一张
//    char left = s1[0];
//    char right = s2[0];
//
//    if (s1.size() == s2.size())
//    {
//        if (sort_poker.find(left) > sort_poker.find(right))
//            return s1;
//        else
//            return s2;
//    }
//    if (s1.size() == 4)
//        return s1;
//    else if (s2.size() == 4)
//        return s2;
//    return "ERROR";
//}
//int main()
//{
//    //string hand;
//    //getline(cin, hand);
//    string left_hand = "4 4 4 4";
//    string right_hand = "joker JOKER";
//    //int i=0;   //先分割左右手牌
//    //for (i = 0; hand[i] != '-'; ++i)
//    //{
//    //    left_hand += hand[i];
//    //}
//    //++i;
//    //for (; i < hand.length(); ++i)
//    //{
//    //    right_hand += hand[i];
//    //}
//    cout << left_hand.length() << endl;
//    cout << right_hand.length() << endl;
//
//    cout << FindMax(left_hand, right_hand) << endl;
//
//    return 0;
//}


//int main()
//{
//    string s = "ABCabc";
//    char ch = 'A';
//    vector<int> arr(127, 0);
//    //getline(cin, s);
//    //cin >> ch;
//
//    //先把所有字符对应ascii码存在数组中
//    for (int i = 0; s[i] != '\0'; ++i)
//    {
//        arr[s[i]]++;
//    }
//    //合并大小写
//    for (int i = 65; i <= 90; ++i)
//    {
//        arr[i] = arr[i] + arr[i + 32];
//    }
//    cout << arr['A' - '0'];
//    return 0;
//}

//int main()
//{
//	cout << 'A' - 0<< endl;
//}

//int main()
//{
//	string s1 = "hello world";
//	cout << s1.length();
//	return 0;
//}


//class A
//
//{
//
//public:
//
//	virtual void f()
//
//	{
//
//		cout << "A::f()" << endl;
//
//	}
//
//};
//
//
//
//class B : public A
//
//{
//
//private:
//
//	virtual void f()
//
//	{
//
//		cout << "B::f()" << endl;
//
//	}
//
//};
//
//int main()
//{
//	A* pa = (A*) new B;
//	pa->f();
//	return 0;
//}

//int cout_drinks(int x)
//{
//    int count = 0;
//    int tmp = 0;
//    int k = 0;
//    while (x / 3)
//    {
//        tmp = x / 3;
//        count += tmp;
//        k = x % 3;
//        x = tmp + k;
//    }
//    if (x == 2)
//        ++count;
//    return count;
//}
//int main()
//{
//    int n = 0;
//    //while (cin >> n)
//    //{
//    //    cout << cout_drinks(n) << endl;
//    //}
//    cout << cout_drinks(10) << endl;
//    return 0;
//}


//// 向下调整法
//void heapify_down(vector<int>& heap, int index) {
//	// 获取左右子节点的索引
//	int left = index * 2 + 1;
//	int right = index * 2 + 2;
//	// 如果左子节点不存在，无需调整
//	if (left >= heap.size()) return;
//	// 找出左右子节点中较大的一个
//	int larger = left;
//	if (right < heap.size() && heap[right] > heap[left]) {
//		larger = right;
//	}
//	// 如果当前节点小于较大的子节点，交换它们的位置，并递归向下调整
//	if (heap[index] < heap[larger]) {
//		swap(heap[index], heap[larger]);
//		heapify_down(heap, larger);
//	}
//}
//
//// 构建堆
//void build_heap(vector<int>& heap) {
//	// 从最后一个非叶子节点开始，依次向下调整
//	for (int i = (heap.size() - 2) / 2; i >= 0; i--) {
//		heapify_down(heap, i);
//	}
//}
//
//int main()
//{
//	vector<int> arr = { 1,8,6,2,5,4,7,3 };
//	build_heap(arr);
//	for (auto k : arr)
//	{
//		cout << k << " ";
//	}
//	return 0;
//}


//int common_count_substring(const string& s1, const string& s2)
//{
//	int count = 0;
//	for (int i = 0; i < s1.length(); ++i)
//	{
//		int max = 0;
//		int flag = 0; 
//		int v = 0;
//		for (int j = 0; j < s2.length(); ++j)
//		{
//			if (s1[i] == s2[j])
//			{
//				for (int k = j; k < s2.length(); ++k)
//				{
//					if (s1[i + v] == s2[k])
//					{
//						++max;
//						++v;
//					}
//					else // s1[i + v] != s2[k]
//					{
//						v = 0;
//						max = 0;
//						if (max > count)
//							count = max;
//					}
//					if (max > count)
//						count = max;
//				}
//			}
//		}
//	}
//    return count;
//}
//int main()
//{
//    string s1 = "ababcdabcdefgcdefg", s2 = "abcdefga";
//   
//    cout << common_count_substring(s1, s2);
//    return 0;
//}


//vector<int> shuffle(vector<int>& arr)
//{
//    int end = arr.size() - 1;
//    int begin = end / 2;
//    vector<int> ret;
//    while (begin >= 0)
//    {
//        ret.push_back(arr[end]);
//        ret.push_back(arr[begin]);
//        --end;
//        --begin;
//    }
//
//    reverse(ret.begin(), ret.end());
//    return ret;
//}
//int main()
//{
//    vector<int> arr;
//    int n;
//    cin >> n;
//    while (n--)
//    {
//        int n, k;
//        cin >> n >> k;
//        while (k--)
//        {
//            for (int i = 0; i < n; ++i)
//            {
//                int key = 0;
//                cin >> key;
//                arr[i] = key;
//            }
//            arr = shuffle(arr);
//        }
//        for (int i = 0; i < n; ++i)
//        {
//            cout << arr[i] << " ";
//        }
//        cout << endl;
//    }
//    return 0;
//}

//int main()
//{
//	vector<int> arr = { 1,2,3,4,5,6 };
//	arr = shuffle(arr);
//	for (auto k : arr)
//	{
//		cout << k << " ";
//	}
//
//	return 0;
//}
// 


//class Person
//{
//public:
//    Person() { ++_count; }
//protected:
//    string _name; // 姓名
//public:
//    static int _count; // 统计人的个数。
//};
//int Person::_count = 0;
//class Student : public Person
//{
//protected:
//    int _stuNum; // 学号
//};
//class Graduate : public Student
//{
//protected:
//    string _seminarCourse; // 研究科目
//};
//void TestPerson()
//{
//    Student s1;
//    Student s2;
//    Student s3;
//    Graduate s4;
//    cout << " 人数 :" << Person::_count << endl;
//    Student::_count = 0;
//    cout << " 人数 :" << Person::_count << endl;
//}
//
//int main()
//{
//	TestPerson();
//	return 0;
//}


//using namespace std;
//class A {
//public:
//	A(char* s) { cout << s << endl; }
//	~A() {}
//};
//class B :virtual public A
//{
//public:
//	B(char* s1, char* s2) :A(s1) { cout << s2 << endl; }
//};
//class C :virtual public A
//{
//public:
//	C(char* s1, char* s2) :A(s1) { cout << s2 << endl; } 
//};
//class D :public B, public C
//{
//public:
//	D(char* s1, char* s2, char* s3, char* s4) :B(s1, s2), C(s1, s3), A(s1)
//	{
//		cout << s4 << endl;
//	}
//};
//int main() {
//	D* p = new D("class A", "class B", "class C", "class D");
//	delete p;
//	return 0;
//}

//using namespace std;
//class A {
//public:
//	A(char* s) { cout << s << endl; }
//	~A() {}
//};
//class B :virtual public A
//{
//public:
//	B(char* s1, char* s2) :A(s1) { cout << s2 << endl; }
//};
//class C :virtual public A
//{
//public:
//	C(char* s1, char* s2) :A(s1) { cout << s2 << endl; }
//};
//class D :public B, public C
//{
//public:
//	D(char* s1, char* s2, char* s3, char* s4) :B(s1, s2), C(s1, s3), A(s1)
//	{
//		cout << s4 << endl;
//	}
//};
//int main() {
//	D* p = new D("class A", "class B", "class C", "class D");
//	delete p;
//	return 0;
//}


//class A
//{
//public:
//	virtual void func(int val = 1)
//	{
//		cout << "A->" << val << endl;
//	}
//	virtual void test()
//	{
//		func();
//	}
//};
//
//class B : public A
//{
//public:
//	void func(int val = 0)
//	{
//		cout << "B->" << val << endl;
//	}
//};
//
//int main()
//{
//	A* p = new B;
//	p->test();
//	return 0;

//int main()
//{
//	cout << "hello" << endl;
//	return 0;
//}


//void RotateR(Node* parent)
//{
//	Node* subL = parent->left;
//	Node* subLR = subL->right;
//
//	parent->left = subLR;
//	if (subLR)
//	{
//		subLR->parent = parnt;
//	}
//
//	Node* ppnode = parenr->parent;
//	subL->right = parent;
//	parent->parent = subL;
//	if (ppnode == nullptr)
//	{
//		_root = subL;
//		subL->parent = nullptr;
//	}
//	else
//	{
//		if (ppnode->left == parent)
//			ppnode->left = subLR;
//		else
//			ppnode->right = sunLR;
//
//		subL->parent = parent;
//	}
//
//	parent->pf = subL->pf = 0;
//}


//struct Compare
//{
//    bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
//    {
//        return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);
//    }
//};
//
//int main()
//{
//    string s1;
//    vector<string> words;
//    getline(cin, s1);
//    // 对字符串进行遍历
//    // 1.遇到大写字母转成小写字母
//    // 2.遇到空格，将前一个单词存起来
//    for (int i = 0; i < s1.length(); ++i)
//    {
//        string str;
//        while (s1[i] != ' ' && s1[i] != '\0')
//        {
//            if (isupper(s1[i]))
//            {
//                str += tolower(s1[i++]);
//            }
//            else {
//                if (s1[i] == '.')
//                    break;
//                str += s1[i++];
//            }
//        }
//
//        words.push_back(str);
//    }
//    map<string, int> countMap;
//    //建map， 存单词和单词出现的个数
//    for (auto& str : words)
//    {
//        countMap[str]++;
//    }
//    //将map中的数据存入vector中
//    //改写仿函数比较方式
//    vector<pair<string, int>> v(countMap.begin(), countMap.end());
//    sort(v.begin(), v.end(), Compare());
//    for (int i = 0; i < v.size(); ++i)
//    {
//        cout << v[i].first << ":" << v[i].second << endl;
//    }
//    return 0;
//}

//int RootOfNum(int x)
//{
//    stack<int> st;
//    while (x >= 10)
//    {
//        //把数字的每一位存入栈中
//        while (x)
//        {
//            st.push(x % 10);
//            x /= 10;
//        }
//
//        int tmp = 0;
//        while (!st.empty())
//        {
//            tmp += st.top();
//            st.pop();
//        }
//        x = tmp;
//    }
//    return x;
//}
//int main()
//{
//    int n;
//    //while (cin >> n)
//    //{
//    //    cout << RootOfNum(n) << endl;
//    //}
//    cout << RootOfNum(10);
//    return 0;
//}

//int main(int number) {
//    // write code here
//    //1.创建dp表
//    //2.初始化dp表
//    //3.状态转移方程
//    //4.返回值
//    int n;
//    cin >> n;
//    vector<int> dp(n + 1);
//    dp[0] = dp[1] = 1;
//    for (int i = 2; i <= n; ++i)
//    {
//        int j = i;
//        while (j - 1 >= 0)
//        {
//            dp[i] += dp[j];
//            j--;
//        }
//        dp[i] += 1;
//    }
//
//    return dp[n];
//}

//struct list_node{
//    int val;
//    struct list_node * next;
//};
//
//list_node * input_list(void)
//{
//    int n, val;
//    list_node * phead = new list_node();
//    list_node * cur_pnode = phead;
//    scanf("%d", &n);
//    for (int i = 1; i <= n; ++i) {
//        scanf("%d", &val);
//        if (i == 1) {
//            cur_pnode->val = val;
//            cur_pnode->next = NULL;
//        }
//        else {
//            list_node * new_pnode = new list_node();
//            new_pnode->val = val;
//            new_pnode->next = NULL;
//            cur_pnode->next = new_pnode;
//            cur_pnode = new_pnode;
//        }
//    }
//    return phead;
//}
//
//
//list_node * reverse_list(list_node * head, int L, int R)
//{
//    //////在下面完成代码
//    list_node* guard = new list_node();
//    guard->next = nullptr;
//    list_node* cur = head;
//    int count = 1;
//    //记录区间的前一个节点和后一个节点
//    list_node* prev = nullptr;
//    list_node* next = nullptr;
//    
//    while(count < L)
//    {
//        prev = cur;
//        cur = cur->next;
//        ++count;
//    }
//        
//    while(count < R)
//    {
//        cur = cur->next;
//        ++count;
//    }
//    next = cur->next;
//    cur->next = nullptr;
//    
//    
//    cur = head;
//    count = 1;
//    while(count < L)
//    {
//        cur = cur->next;
//        ++count;
//    }
//    
//    //反转链表
//    count = L;
//    while(cur && L <= R)
//    {
//        list_node* tmp = cur->next;
//        cur->next = guard->next;
//        guard->next = cur;
//        cur = tmp;
//    }
//    //链接链表区间前后部分
//    if(L != 1)
//        prev->next = guard->next;
//    cur = guard->next;
//    count = L;
//    while(count < R)
//    {
//        cur = cur->next;
//        ++count;
//    }
//    cur->next = next;
//    if(L == 1)
//        return guard->next;
//    else
//        return head;
//}
//
//void print_list(list_node * head)
//{
//    while (head != NULL) {
//        printf("%d ", head->val);
//        head = head->next;
//    }
//    puts("");
//}
//
//
//int main ()
//{
//    int L, R;
//    list_node * head = input_list();
//    scanf("%d%d", &L, &R);
//    list_node * new_head = reverse_list(head, L, R);
//    print_list(new_head);
//    return 0;
//}

//#include <iostream>
//#include <vector>
//#include <string>
//
//using namespace std;
//
//int main()
//{
//    string str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
//    string s;
//    while (cin >> s)
//    {
//        string tmp;
//        for (int i = 0; i < s.size(); ++i)
//        {
//            if (s[i] == ' ')
//                tmp += ' ';
//            else
//            {
//                tmp += str[((s[i] - 'A' + 5) % 26)];
//            }
//        }
//        cout << tmp;
//    }
//
//    return 0;
//}

//class A
//{
//public:
//	A()
//	{}
//
//	A(int) = delete;
//};
//int main()
//{
//	return 0;
//}


//[14, 15, 16, 22, 53, 60]
//76

//vector<int> twoSum(vector<int>& nums, int target) {
//    //暴力
//    vector<int> ret(2);
//    for (int i = 0; i < nums.size() - 2; ++i)
//    {
//        for (int j = i + 1; j < nums.size(); ++j)
//        {
//            if (nums[i] + nums[j] == target)
//            {
//                ret[0] = nums[i];
//                ret[1] = nums[j];
//                return ret;
//            }
//        }
//    }
//    return ret;
//}
//
//int main()
//{
//    vector<int> ret(2);
//    vector<int> arr = { 14, 15, 16, 22, 53, 60 };
//    ret = twoSum(arr, 76);
//    for (int i = 0; i <= 1; ++i)
//    {
//        cout << ret[i] << " ";
//    }
//    return 0;
//}

//int main()
//{
//	//1.t1 先运行，t2后运行
//	//2.两个线程交替运行
//
//	mutex mtx;
//	condition_variable cv;
//
//	int n = 100;
//	int x = 1;
//
//
//	thread t1([&, n]() {
//		while (1)
//		{
//			unique_lock<mutex> lock(mtx);
//			if (x >= 100)
//				break;
//
//			//if (x % 2 == 0) //偶数阻塞
//			//{
//			//	cv.wait(lock);
//			//}
//			cv.wait(lock, [&x]() {return x % 2 != 0; });
//
//			cout << this_thread::get_id() << ":" << x << endl;
//			++x;
//
//			cv.notify_one();
//		}
//		});
//
//	thread t2([&, n]() {
//		while (1)
//		{
//			unique_lock<mutex> lock(mtx);
//			if (x >= 100)
//				break;
//
//			//if (x % 2 == 1) //奇数阻塞
//			//{
//			//	cv.wait(lock);
//			//}
//			cv.wait(lock, [&x]() {return x % 2 != 1; });
//
//			cout << this_thread::get_id() << ":" << x << endl;
//			++x;
//
//			cv.notify_one();
//		}
//		});
//
//	t1.join();
//	t2.join();
//	
//	return 0;
//}

//int main()
//{
//	mutex mtx;
//	condition_variable cv;
//
//	int n = 100;
//	int x = 1;
//
//	// 问题1：如何保证t1先运行，t2阻塞？
//	// 问题2：如何防止一个线程不断运行？
//	thread t1([&, n]() {
//		while (1)
//		{
//			unique_lock<mutex> lock(mtx);
//			if (x >= 100)
//				break;
//
//			//if (x % 2 == 0) // 偶数就阻塞
//			//{
//			//	cv.wait(lock);
//			//}
//			cv.wait(lock, [&x]() {return x % 2 != 0; });
//
//			cout << this_thread::get_id() << ":" << x << endl;
//			++x;
//
//			cv.notify_one();
//		}
//		});
//
//	thread t2([&, n]() {
//		while (1)
//		{
//			unique_lock<mutex> lock(mtx);
//			if (x > 100)
//				break;
//
//			//if (x % 2 != 0) // 奇数就阻塞
//			//{
//			//	cv.wait(lock);
//			//}
//			cv.wait(lock, [&x](){return x % 2 == 0; });
//
//
//			cout << this_thread::get_id() << ":" << x << endl;
//			++x;
//
//			cv.notify_one();
//		}
//		});
//
//	t1.join();
//	t2.join();
//
//	return 0;
//}

//vector<string> uncommonFromSentences(string s1, string s2)
//{
//    map<string, int> wordcount;
//    vector<string> ret;
//    string tmp;
//
//    for (int i = 0; i < s1.size(); ++i)
//    {
//        tmp = "";
//        while (s1[i] != ' ' && s1[i] != '\0')
//        {
//            tmp += s1[i];
//            i++;
//        }
//        wordcount[tmp]++;
//    }
//
//    for (int i = 0; i < s2.size(); ++i)
//    {
//        tmp = "";
//        while (s2[i] != ' ' && s2[i] != '\0')
//        {
//            tmp += s2[i];
//            ++i;
//        }
//        wordcount[tmp]++;
//    }
//    for (auto& e : wordcount)
//    {
//        if (e.second == 1)
//            ret.push_back(e.first);
//    }
//
//    return ret;
//}
//
//int main()
//{
//    string s1 = "this apple is sweet", s2 = "this apple is sour";
//    vector<string> ret;
//    ret = uncommonFromSentences(s1, s2);
//    for (int i = 0; i < ret.size(); ++i)
//    {
//        cout << ret[i] << endl;
//    }
//    return 0;
//}

//bool isAnagram(string s, string t) {
//    if (s.length() != t.length())
//        return false;
//
//    vector<int> v1(26);
//    vector<int> v2(26);
//
//    for (int i = 0; i < s.size(); ++i)
//    {
//        v1[s[i] - 'a']++;
//    }
//
//    for (int i = 0; i < t.size(); ++i)
//    {
//        v2[s[i] - 'a']++;
//    }
//
//    for (int i = 0; i < v1.size(); ++i)
//    {
//        if (v1[i] != v2[i])
//            return false;
//    }
//    return true;
//}
//
//int main()
//{
//    string s = "anagram";
//    string t = "nagaram";
//    cout << isAnagram(s, t) << endl;
//
//    return 0;
//}


//bool halvesAreAlike(string s) {
//    //全部转换成小写
//    for (int i = 0; i < s.size(); ++i)
//    {
//        s[i] = tolower(s[i]);
//    }
//    int size = s.size();
//    int n1=0, n2=0;
//    for (int i = 0; i < size / 2; ++i)
//    {
//        if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i'
//            || s[i] == 'o' || s[i] == 'u')
//        {
//            ++n1;
//        }
//    }
//
//    for (int i = size / 2; i < size; ++i)
//    {
//        if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i'
//            || s[i] == 'o' || s[i] == 'u')
//        {
//            ++n2;
//        }
//    }
//    return n1 == n2;
//
//}
//int main()
//{
//    string s = "book";
//    cout << halvesAreAlike(s) << endl;
//    return 0;
//}


//operator= (const shard_ptr<T>& sp)
//{
//	//两个指针指向同一个资源
//	if (_ptr == sp.ptr)
//		return _ptr;
//	//两个指针指向不同资源
//	if ((--*(_count ) == 0) && _ptr)
//	{
//		delete _ptr;
//		delete _count;
//	}
//	_ptr = sp._ptr;
//	_count = sp.count;
//	*(_count)++;
//
//	return *this;
//}

//class A
//
//{
//
//public:
//
//	A() {}
//
//};
//
//
//
//void foo()
//
//{
//	throw new A;
//}
//
//int main()
//{
//	try
//	{
//		foo();
//	}
//	catch (A* x)
//	{
//		cout << "hllo" << endl;
//	}
//	return 0;
//}

//int main()
//{
//	int count = 0;
//	for (int x = 0, y = 0; (y = 123) && (x < 4); x++)
//	{
//		++count;
//	}
//	cout << count;
//}



//int main() {
//    string s1, s2;
//    string ret;
//    
//    cin >> s1;
//    cin >> s2;
//
//    ret = "";
//    vector<int> words(52);
//    //将字符二中字母的ascii码值存入words中映射
//    for (int i = 0; i < s2.length(); ++i)
//    {
//        words[s2[i] - 'a'] = 1;
//    }
//
//    for (int i = 0; i < s1.length(); ++i)
//    {
//        if (words[s1[i] - 'a'] == 0)
//            ret += s1[i];
//    }
//
//    cout << ret;
// 
//}

//int maxPower(string s) {
//    int len = 1;
//    int max = 0;
//    for (int i = 0; i < s.length(); ++i)
//    {
//        if (s[i] == s[i + 1])
//        {
//            ++len;
//            if (len >= max)
//                max = len;
//        }
//        else // s[i] == s[i+1]
//        {
//            len = 1;
//        }
//    }
//    return max;
//}
//
//int main()
//{
//    string s = "leetcode";
//    cout << maxPower(s) << endl;
//    return 0;
//}

//class A
//{
//public:
//	A(int x)
//	{
//		cout << 1 << endl;
//	}
//
//};
//int main()
//{
//	A a(4), b(5), c(3), * p[2] = { &a, &b };
//}

//int main()
//{
//    string s1 = "i like beijing";
//    stack<string> st;
//    //getline(cin, s1);
//    string tmp = "";
//    for (int i=0; i<s1.size(); ++i)
//    {
//        if (s1[i] != ' ' && s1[i] != '\0')
//        {
//            tmp += s1[i];
//        }
//        else //ch != ' ' && ch != '\0' 
//        {
//            st.push(tmp);
//            tmp = "";
//        }
//
//    }
//    st.push(tmp);
//    while (!st.empty())
//    {
//        cout << st.top() << " ";
//        st.pop();
//    }
//    cout << endl;
//    return 0;
//}

//int main()
//{
//	int a[4] = { 1,2,3,4 };
//	int* ptr = (int*)(&a + 1);
//	printf("%d", *(ptr - 1));
//
//	//cout << sizeof(acx) << sizeof(acy) << endl;
//	return 0;
//}

//int main()
//{
//	int m = 0123, n = 123;
//	printf("%o, %o\n", m, n);
//	return 0;
//}

//

//class A
//{
//public:
//	A(int aa, int bb)
//		:_a(aa--)
//		,_b(_a*bb)
//	{}
//public: 
//	int _a;
//	int _b;
//};
//
//int main()
//{
//	A x(4, 5);
//	cout << x._a << x._b << endl;
//	return 0;
//}


//int getLCA(int a, int b) {
//    // write code here
//    int Max = max(a, b);
//    vector<int> v(Max);
//    //初始化    
//    for (int i = 0; i < Max; ++i)
//    {
//        v[i] = i + 1;
//    }
//
//    //将根到节点的路径存在list里
//    queue<int> q1;
//    queue<int> q2;
//
//    while (a)
//    {
//        q1.push(a);
//        a = a / 2;
//    }
//
//    while (b)
//    {
//        q2.push(b);
//        b = b / 2;
//    }
//
//    while (q1.size() != q2.size())
//    {
//        if (q1.size() > q2.size())
//        {
//            q1.pop();
//        }
//        else if (q1.size() < q2.size())
//        {
//            q2.pop();
//        }
//    }
//
//    //此时长度相等，转换成最短路径相交
//    while (q1.front() != q2.front())
//    {
//        q1.pop();
//        q2.pop();
//    }
//    //此时就是祖先
//    return q1.front();
//}
//
//int main()
//{
//    cout << getLCA(15, 4) << endl;
//    return 0;
//}

//bool is_Prime_number(int x) //判断素数
//{
//    for (int i = 2; i < x; ++i)
//    {
//        if (x % i == 0)
//            return false;
//    }
//
//    return true;
//}
//
//int main()
//{
//    vector<int> pn;
//    vector<int> ret(2);
//    pn.push_back(1);
//    pn.push_back(2);
//    pn.push_back(3);
//
//     for (int i = 4; i < 1000; ++i)
//    {
//        if (is_Prime_number(i))
//            pn.push_back(i);
//    }
//
//    int n;
//    cin >> n;
//    int begin = 0;
//    int end = pn.size() - 1;
//
//    while (begin < end)
//    {
//        if (pn[begin] + pn[end] == n)
//        {
//            ret[0] = pn[begin];
//            ret[1] = pn[end];
//        }
//        ++begin;
//        --end;
//    }
//    cout << ret[0] << endl << ret[1] << endl;
//}

//class B
//{
//public:
//	B()
//	{
//		cout << "default" << " ";
//	}
//	~B()
//	{
//		cout << "destr" << " ";
//	}
//
//	B(int i) :data(i)
//	{
//		cout << "con " << " ";
//	}
//	int data;
//};
//
//B play(B b)
//{
//	return b;
//}
//
//int main()
//{
//	B temp = play(5);
//	return 0;
//}

//int main() {
//    string s = "xcopy /s c:\\ d:\\e";
//    //cin >> s;
//    vector<string> ret;
//
//    for (int i = 0; i < s.size(); ++i)
//    {
//        string tmp = "";
//        while (s[i] != ' ' && s[i] != '"' && i<s.size())
//        {
//            tmp += s[i];
//            ++i;
//        }
//        ret.push_back(tmp);
//        tmp = "";
//        if (s[i] == ' ')
//            continue;
//        else if (s[i] == '"')
//        {
//            ++i;
//            while (s[i] != '"')
//            {
//                tmp += s[i];
//            }
//            ret.push_back(tmp);
//        }
//    }
//
//    cout << ret.size() << endl;
//    for (size_t i = 0; i < ret.size(); ++i)
//    {
//        cout << ret[i] << endl;
//    }
//
//
//    return 0;
//}

//struct A
//{
//	void foo() { cout << "foo"; }
//	virtual void bar() { cout << "bar"; }
//	A() { bar(); }
//};
//
//struct B :A
//{
//	void foo() { cout << "b_foo"; }
//	void bar() { cout << "b_bar"; }
//};
//
//int main()
//{
//	B b;
//	A* ptr = (A*)&b;
//	ptr->foo();
//	ptr->bar();
//	return 0;
//}

//class A
//{
//public:
//	A() { cout << "A "; }
//	~A() { cout << "deA "; }
//};
//
//class B
//{
//public:
//	B() { cout << "B "; }
//	~B() { cout << "deB "; }
//};
//
//class C : public A, public B
//{
//public:
//	C() { cout << "C "; }
//	~C() { cout << "deC "; }
//};
//
//int main()
//{
//	A* a = new C();
//	delete a;
//	return 0;
//}

//int giveGem(vector<int>& gem, vector<vector<int>>& operations) {
//	for (int i = 0; i < operations.size(); ++i)
//	{
//		int count = gem[operations[i][0]] / 2;
//		gem[operations[i][1]] += count;
//		gem[operations[i][0]] -= count;
//	}
//	sort(gem.begin(), gem.end());
//	return gem[gem.size()-1] - gem[0];
//
//}
//
//int main()
//{
//	vector<int> gem = { 3,1,2 };
//	vector<vector<int>>  operations = { {0, 2} ,{2, 1},{2, 0} };
//
//	cout << giveGem(gem, operations) << endl;
//	return 0;
//}


//#include <iostream>
//#include <vector>
//#include <string>
//using namespace std;
//
//int Length(const string& s)
//{
//    vector<char> ret;
//    for (size_t i = 0; i < s.size(); ++i)
//    {
//        if (s[i] != '-' && s[i] != '\0')
//            ret.push_back(s[i]);
//    }
//
//    return ret.size();
//}
//
//string Winner(const string& s)
//{
//    string left = "";
//    string right = "";
//    for (int i = 0; i < s.size(); ++i)
//    {
//        while (s[i] != '-')
//        {
//            left += s[i++];
//        }
//
//        ++i;
//        while (s[i] != '\0')
//        {
//            right += s[i++];
//        }
//    }
//    int left_length = Length(left);
//    int right_length = Length(left);
//    if (left == "joker JOKER" || right == "joker JOKER")
//        return "joker JOKER";
//    else if (left_length == right_length)
//    {
//        return left[0] > right[0] ? left : right;
//    }
//    else if (left_length == 4 && left_length != 4)
//    {
//        return left;
//    }
//    return "ERROR";
//}
//
//int main() {
//    string s = ;
//    while (cin >> s)
//    {
//        cout << Winner(s) << endl;
//    }
//}
// 64 位输出请用 printf("%lld")


//int main()
//{
//    int n;
//
//    while (cin >> n)
//    {
//        vector<vector<int>> vv(n);
//        //初始化
//        for (int i = 0; i < vv.size(); ++i)
//        {
//            vv[i].resize(4 + i*2);
//            vv[i][1] = 1;
//            vv[i][i * 2 + 1] = 1;
//
//            for (int j = 2; j < i * 2 + 1; ++j)
//            {
//                vv[i][j] = vv[i - 1][j - 2] + vv[i - 1][j - 1] + vv[i - 1][j];
//            }
//        }
//
//        int flag = 0;
//        for (int i = 1; i < vv[n - 1].size(); ++i)
//        {
//            if (vv[n - 1][i] % 2 == 0)
//            {
//                cout << i << endl;
//                flag = 1;
//                break;
//            }
//        }
//        if (flag == 0)
//            cout << -1 << endl;
//    }
//    return 0;
//}


//int main() {
//	string s = "ABCabc";
//	char ret = 'A';
//	int count[26] = {0};
//
//	//getline(cin, s);
//	//cin >> ret;
//	for (auto& e : s) {
//		if (isalpha(e))
//			count[tolower(e) - 97]++;
//	}
//	cout << count[tolower(ret) - 97];
//
//}

//int main()
//{
//	while (int i = 0)
//	{
//		cout << i-- << endl;
//	}
//	return 0;
//}


//#include <iostream>
//
//using namespace std;
//
//void Myprintf()
//{
//    cout << endl;
//}
//
//template<typename T, typename ...Args>
//void Myprintf(const T& v, Args&&...args)
//{
//    cout << v;
//    if ((sizeof ...(args)) > 0)
//    {
//        //参数包个数不为0
//        Myprintf(forward<Args>(args)...);
//    }
//    else {
//        Myprintf();
//    }
//}
//
//int main()
//{
//    Myprintf("比特");
//    Myprintf("比特", "就业课");
//
//    return 0;
//}

//class Singleton
//{
//public:
//    static Singleton& GetInstance()
//    {
//        return _eton;
//    }
//    int getData() { return _data; }
//
//private:
//    Singleton(int data = 99) :_data(data)
//    {
//        std::cout << "单例对象实例化" << std::endl;
//    }
//    ~Singleton() {}
//    Singleton(const Singleton&) = delete;
//    static Singleton _eton;
//
//private:
//    int _data;
//};
//
//Singleton Singleton::_eton;
//
//int main()
//{
//    std::cout << Singleton::GetInstance().getData() << std::endl;
//    return 0;
//}


//class Computer
//{
//public:
//    Computer() {}
//    void setBoard(const std::string& board) {
//        _board = board;
//    }
//    void setDisplay(const std::string& display) {
//        _display = display;
//    }
//    virtual void setOs()
//    {}
//
//protected:
//    std::string _board;
//    std::string _display;
//    std::string _os;
//};
//
//class MacComputer : public Computer {
//public:
//    void setOs() override
//    {
//        _os = "Max OS x12";
//    }
//
//};
//int main()
//{
//    MacComputer mcp;
//    return 0;
//}


//int main() {
//    string s = "asdfasdfo";
//    unordered_map<char, int> map;
//   
//    for (auto& c : s) {
//        map[c]++;
//    }
//    int flag = 0;
//    for (auto& c : s) {
//        if (map[c] == 1) {
//            cout << c << endl;
//            flag = 1;
//            break;
//        }
//    }
//    if (flag == 0) cout << -1 << endl;
//}

//int main() {
//    int n;
//    while (cin >> n) 
//    {
//        int count = 0;
//        int max = 0;
//        vector<string> v = { "A connect", "A disconnect"
//                           , "B connect", "C connect"
//                           , "B disconnect", "C disconnect"};
//   
//        for (auto& str : v) {
//            if (str[2] == 'c') {
//                ++count;
//                if (count > max) max = count;
//            }
//            else if (str[2] == 'd') --count;
//        }
//        cout << max << endl;
//    }
//}

//#include <memory>
//#include <fstream>
//
//namespace log {
//    class logSink {
//    public:
//        using ptr = std::shared_ptr<logSink>;
//        logSink() {}
//        virtual ~logSink() {};
//        virtual void log() { const char* data, int len = 0 } ;= 0;
//    };
//    //落地方向：标准输出
//    class StdoutSink : public logSink {
//    public:
//        //将日志消息写入到标准输出
//        void log() { const char* data, size_t len };
//    };
//    //落地方向：指定文件
//    class FileSink : public logSink {
//    public:
//        FileSink(const std::string& pathname) {}
//        void log() { const char* data, size_t len };
//    private:
//        std::string _pathname;
//        std::ofstream _ofs;
//    };
//    //落地方向：滚动文件
//    class RollBySizeSink : public logSink {
//    public:
//        RollBySizeSink(const std::string& basename, size_t max_size) {}
//        void log() { const char* data, size_t len };
//    private:
//        void createNewFile();//进行大小判断，超过指定大小创建新文件
//    private:
//        //通过基础文件名 + 拓展文件名（以时间生成的）组成的一个实际的当前输出文件名
//        std::string _basename; // ./logs/base-
//        std::ofstream _ofs;
//        size_t _max_fsize; //记录文件存储的最大大小
//        size_t _cur_fsize; //记录当前文件大小
//    };
//}


//判断大小端字节序
//
//int main() {
//	int a = 0x12345678;
//	char* p = (char*)&a;
//	if (*p == 0x12)
//		cout << "大端";
//	else if (*p == 0x78)
//		cout << "小段";
//
//	return 0;
//}

//int main() {
//    int n;
//
//    while (cin >> n) {
//        char tmp;
//        stack<char> st_num;
//        stack<char> st_op;
//        for (int i = 0; i < n; ++i) {
//            cin >> tmp;
//            if (tmp > '0' && tmp < '9') { //数字入栈
//                st_num.push(tmp);
//            }
//            else { //操作字符入栈
//                st_op.push(tmp);
//            }
//        }
//
//        //
//
//        while (!st_op.empty()) {
//            char op = st_op.top();
//            st_op.pop();
//            int top = st_num.top() - '0';
//            st_num.pop();
//            switch (op) {
//            case '+':
//                top = top + (st_num.top() - '0');
//                break;
//            case '-':
//                top = top - (st_num.top() - '0');
//                break;
//            case '*':
//                top = top * (st_num.top() - '0');
//                break;
//            case '/':
//                top = top * (st_num.top() - '0');
//                break;
//            };
//            st_num.push(top);
//        }
//        cout << st_num.top() << endl;
//
//    }
//}




//int main() {
//	int n;
//	while (cin >> n) 
//	{
//		stack<char> st_num;
//		stack<char> st_op;
//
//		char tmp;
//		for (int i = 0; i < n; ++i) {
//			cin >> tmp;
//			if (tmp > '0' && tmp < '9') {
//				st_num.push(tmp);
//			}
//			else {
//				char op = tmp;
//				int ritht_num = st_num.top() - '0';
//				st_num.pop();
//				int left_num = st_num.top() - '0';
//				st_num.pop();
//
//				int top;
//				switch (op) {
//				case('+'):
//					top = ritht_num + left_num;
//					break;
//				case('-'):
//					top = ritht_num - left_num;
//					break;
//				case('*'):
//					top = ritht_num * left_num;
//					break;
//				case('/'):
//					top = ritht_num / left_num;
//					break;
//				};
//				st_num.push(top + '0');
//			}
//		}
//		
//		cout << st_num.top() << endl;
//	}
//
//	
//}

//string cal(const string& num1, const string& num2) {
//
//}
//
//int main() {
//	int n;
//	while (cin >> n) 
//	{
//		stack<string> st_num;
//		stack<char> st_op;
//
//		char tmp;
//		for (int i = 0; i < n; ++i) {
//			cin >> tmp;
//			if (tmp > '0' && tmp < '9') {
//				st_num.push(tmp);
//			}
//			else {
//				char op = tmp;
//				int ritht_num = st_num.top() - '0';
//				st_num.pop();
//				int left_num = st_num.top() - '0';
//				st_num.pop();
//
//				int top;
//				switch (op) {
//				case('+'):
//					top = ritht_num + left_num;
//					break;
//				case('-'):
//					top = ritht_num - left_num;
//					break;
//				case('*'):
//					top = ritht_num * left_num;
//					break;
//				case('/'):
//					top = ritht_num / left_num;
//					break;
//				};
//				st_num.push(top + '0');
//			}
//		}
//		
//		cout << st_num.top()-'0' << endl;
//	}
//
//	
//}

//int main() {
//    string s = "I am a student";
//    //while (getline(cin, s)) {
//        string tmp = "";
//        stack<string> st;
//
//        for (int i = 0; i < s.size(); ++i) {
//            tmp = "";
//            while (isalpha(s[i])) {
//                tmp += s[i];
//                ++i;
//            }
//            if (tmp.size() != 0)
//                st.push(tmp);
//        }
//        for (int i = 0; i < st.size(); ++i) {
//            cout << st.top();
//            st.pop();
//        }
//        cout << endl;
//    //}
//}


//分割组合
void f(string& str) {
	string tmp = "";
	for (int i = 0; i < str.size(); ++i) {
		if (str[i] != '&') tmp += str[i];
		else ++i;
		
	}
	std::cout << tmp << std::endl;
}

int main() {
	string str = "ab&&ce&&a";
	f(str);
	return 0;
}


//找最大质数
//int num(int x) {
//	vector<int> v;
//	int max = 0;
//	for (int i = 2; i < x; ++i) {
//		for (int j = 2; j <= i; j++) {
//			if (i % j == 0) {
//				break;
//			}
//			if (j == i)
//				max = j;
//		}
//		
//	}
//	return max;
//}
//int main() {
//	int n;
//	cin >> n;
//	int max = num(n);
//	cout << max << endl;
//
//}



////找相同数
//int num(vector<int>& v) {
//	unordered_map<int, int> map;
//	for (int i = 0; i < v.size(); ++i) {
//		map[i]++;
//	}
//	int dou_num;
//	auto it = map.begin();
//	while (it != map.end()) {
//		if (it->second == 2) {
//			dou_num = it->first;
//		}
//	}
//	return dou_num;
//}


////质数
//int num(int x) {
//	if (x <= 2)	return 0;
//	if (x == 3) return 1;
//
//	int ret = 0;
//	for (int i = 3; i < x; ++i) {
//		for (int j = 2; j < i; ++j) {
//			if (i % j == 0) {
//				break;
//			}
//		}
//		if
//	}
//}